package com.haven123.cloudapp.common.data;

import java.util.Stack;

public class TreeA {
    public class Node{
        public int iData;
        public double fData;
        public Node leftChild;
        public Node rightChild;

        public void dispalyNode(){
            System.out.println(fData);
        }
    }
    public  Node root;

    /**
     * 和二分查找有点相识哦，
     * @param key
     * @return
     */
    public Node find(int key){
        Node current=root;
        while (current.iData!=key){
            if(key<current.iData){
                current=current.leftChild;
            }else{
                current=current.rightChild;
            }
            if(current==null){
                return null;
            }
        }
        return current;
    }
    public Node findparent(int key){
        Node current=root;
        Node parent=null;
        while (current.iData!=key){
            parent=current;
            if(key<current.iData){
                current=current.leftChild;
            }else{
                current=current.rightChild;
            }
            if(current==null){
                return null;
            }
        }
        return parent;
    }

    public void insert(int id,double dd){
        Node node=new Node();
        node.iData=id;
        node.fData=dd;
        if(root==null){
            root=node;
        }else{
            Node current=root;
            Node parent;
            while (true){
                parent=current;
                if(id<current.iData){
                    current=current.leftChild;
                    if(current==null){
                        parent.leftChild=node;
                        return;
                    }
                }else{
                    current=current.rightChild;
                    if(current==null){
                        parent.rightChild=node;
                        return;
                    }
                }
            }
        }
    }
    public void displaya(){
        inOrder(root);
    }
    public void dispalyTree(){
        Stack globalStack=new Stack();
        globalStack.push(root);
        int nBlanks=64;
        boolean isRowEmpty =false;
        System.out.println(
                "-----------------------------root------------------------------"
        );
        while (isRowEmpty==false){
            Stack localStack=new Stack();
            isRowEmpty=true;
            for(int j=0;j<nBlanks;j++){
                System.out.print(" ");
            }
            while (globalStack.isEmpty()==false){
                Node temp=(Node)globalStack.pop();
                if(temp!=null){
                    System.out.print(temp.iData);
                    localStack.push(temp.leftChild);
                    localStack.push(temp.rightChild);
                    if(temp.leftChild!=null||temp.rightChild!=null){
                        isRowEmpty=false;
                    }
                }else{
                    System.out.print("**");
                    localStack.push(null);
                    localStack.push(null);
                }
                for(int j=0;j<nBlanks*2-2;j++){
                    System.out.print(" ");
                }
            }
            System.out.println();
            nBlanks/=2;
            while (localStack.isEmpty()==false){
                globalStack.push(localStack.pop());
            }
        }
        System.out.println(
                "-----------------------------------------------------------"
        );
    }
    private void inOrder(Node localRoot){
        if(localRoot!=null){
            inOrder(localRoot.leftChild);
            System.out.println("id: "+localRoot.iData+" leftID:"+(localRoot.leftChild==null?' ':localRoot.leftChild.iData)+" rightID: "+(localRoot.rightChild==null?' ':localRoot.rightChild.iData));
            inOrder(localRoot.rightChild);
        }
    }

    /**
     * 删除一个指定的节点
     * @param id
     */
    public void delete(int id){
        Node node = find(id);
        Node findparent = findparent(id);
        boolean isLeftChild=false;
        if(findparent!=null){
            isLeftChild =findparent.leftChild==node;
        }
        if(node.leftChild==null&&node.rightChild==null){
            if(node==root){
                root=null;
            }else{
                if(isLeftChild){
                    findparent.leftChild=null;
                }else{
                    findparent.rightChild=null;
                }
            }
        }else if(node.rightChild==null){
            if(node==root){
                root=node.leftChild;
            }else if(isLeftChild){
                findparent.leftChild=node.leftChild;
            }else{
                findparent.rightChild=node.leftChild;
            }
        }else if(node.leftChild==null){
            if(node==root){
                root=node.rightChild;
            }else if(isLeftChild){
                findparent.leftChild=node.rightChild;
            }else{
                findparent.rightChild=node.rightChild;
            }
        }else{
            Node sub = getSub(node);
            if(node==root){
                root=sub;root.leftChild=node.leftChild;
            }else if(isLeftChild){
                findparent.leftChild=sub;
            }else{
                findparent.rightChild=sub;
                sub.leftChild=node.leftChild;
            }
        }

    }
    private  Node getSub(Node node){
        Node parent=node;
        Node sub=node;
        Node current=node.rightChild;
        while (current!=null){
            parent=sub;
            sub=current;
            current=current.leftChild;
        }
        if(sub!=node.rightChild){
            parent.leftChild=sub.rightChild;
            sub.rightChild=node.rightChild;
        }
        return sub;
    }
}
